#include <vector>
#include <string>
#include <iostream>
#include "../linkedlist/single_track/linkedlist.hpp"

using namespace std;

class Graph {
private:
    // 结点集合
    vector<string> vertexList;
    // 邻接矩阵
    int **edges;
    // 边数目
    int edges_num;
    // 记录结点是否被访问
    bool *visit_res;

    // 获取第一个邻接结点的下标
    int get_first_ngb(int index) {
        int n = size();
        for (int i = 0; i < n; i++) {
            if (edges[index][i] == 1)
                return i;
        }
        return -1;
    }
    // 获取下一个邻接结点
    int get_next_ngb(int v1, int v2) {
        for (int j = v2 + 1; j < size(); j++) {
            if (edges[v1][j] == 1)
                return j;
        }
        return -1;
    }
    // 对结点进行深度优先遍历
    void dfs(int i) {
        cout << vertexList[i] << " -> ";
        visit_res[i] = true;
        int w = get_first_ngb(i);
        while(w != -1) {
            if (!visit_res[w])
                dfs(w);
            w = get_next_ngb(i, w);
        }
    }
    // 对结点进行广度优先遍历
    void bfs(int i) {
        // 队列的头节点对应下标
        int u;
        // 邻接结点
        int w;
        // 记录结点访问顺序的队列
        LinkedList<int> queue;

        cout << vertexList[i] << " -> ";
        visit_res[i] = true;
        queue.push_back(i);

        while (!queue.empty()) {
            u = queue.head();
            queue.pop_front();
            
            w = get_first_ngb(u);
            while(w != -1) {
                if (!visit_res[w]) {
                    cout << vertexList[w] << " -> ";
                    visit_res[w] = true;
                    queue.push_back(w);
                }
                w = get_next_ngb(u, w);
            }
        }
    }
public:
    Graph(int n) {
        edges = new int*[n];
        for (int i = 0; i < n; i++)
            edges[i] = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                edges[i][j] = 0;
        }

        edges_num = 0;

        

    }
    ~Graph() {
        

        int n = size();
        for (int i = 0; i < n; i++)
            delete edges[i];
        delete edges;

        delete visit_res;
    }
    // 返回结点个数
    int size() {
        return vertexList.size();
    }
    // 返回边的数目
    int get_num_edges() {
        return edges_num;
    }
    // 插入结点
    void insert_vertex(string vertex) {
        vertexList.push_back(vertex);
    }
    // 添加边
    void insert_edge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        edges_num++;
    }
    // 输出矩阵
    void show() {
        int n = size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                cout << edges[i][j] << " ";
            cout << endl;        
        }
    }
    // 深度优先遍历
    void traverse_dfs() {
        int n = size();
        visit_res = new bool[n];
        for (int i = 0; i < n; i++)
            visit_res[i] = false;
        
        for (int i = 0; i < n; i++) {
            if (!visit_res[i])
                dfs(i);
        }
        cout << endl;
        delete visit_res;
        visit_res = nullptr;
    }
    // 广度优先遍历
    void traverse_bfs() {
        int n = size();
        visit_res = new bool[n];
        for (int i = 0; i < n; i++)
            visit_res[i] = false;
        
        for (int i = 0; i < n; i++) {
            if (!visit_res[i])
                bfs(i);
        }
        cout << endl;
        delete visit_res;
        visit_res = nullptr;
    }
};